package com.datastructures2.字符串.字符串排序;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 低位优先的字符串排序
 * @author MaoLin Wang
 * @date 2020/2/2515:51
 */
public class LSD {
    public static void sort(String[]a,int w){
        //通过前w个字符将a[]排序
        int N=a.length;
        int R=256;

        String[] aux=new String[N];
        for (int d = w-1; d >=0 ; d--) {
            //根据第d个字符用键索引计数法排序
            int[] count=new int[R+1];
            //计算出现频率
            for (int i = 0; i < N; i++) {
                count[a[i].charAt(d)+1]++;
            }
            //将频率转换为索引
            for (int r = 0; r < R; r++) {
                count[r+1] += count[r];
            }
            //元素分类
            for (int i = 0; i < R; i++) {
                aux[count[a[i].charAt(d)]++]=a[i];
            }
            //回写
            for (int i = 0; i < N; i++) {
                a[i]=aux[i];
            }
        }
    }

    public static void main(String[] args) {

        List<Map<String,String>> list=new ArrayList<>();
        Map<String,String>map1=new HashMap<>();
        map1.put("1","2");
        map1.put("2","5");
        list.add(map1);
        Map<String,String>map2=new HashMap<>();
        map2.put("1","1");
        map2.put("2","3");
        map2.put("3","4");
        list.add(map2);
    }
}
